package com.sheng.leetcode.year2022.month06.day24;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author liusheng
 * @date 2022/06/24
 *
 * 2094. 找出 3 位偶数
 *
 * 给你一个整数数组 digits ，其中每个元素是一个数字（0 - 9）。数组中可能存在重复元素。
 * 你需要找出 所有 满足下述条件且 互不相同 的整数：
 * 该整数由 digits 中的三个元素按 任意 顺序 依次连接 组成。
 * 该整数不含 前导零
 * 该整数是一个 偶数
 * 例如，给定的 digits 是 [1, 2, 3] ，整数 132 和 312 满足上面列出的全部条件。
 * 将找出的所有互不相同的整数按 递增顺序 排列，并以数组形式返回。
 *
 * 示例 1：
 * 输入：digits = [2,1,3,0]
 * 输出：[102,120,130,132,210,230,302,310,312,320]
 * 解释：
 * 所有满足题目条件的整数都在输出数组中列出。
 * 注意，答案数组中不含有 奇数 或带 前导零 的整数。
 *
 * 示例 2：
 * 输入：digits = [2,2,8,8,2]
 * 输出：[222,228,282,288,822,828,882]
 * 解释：
 * 同样的数字（0 - 9）在构造整数时可以重复多次，重复次数最多与其在 digits 中出现的次数一样。
 * 在这个例子中，数字 8 在构造 288、828 和 882 时都重复了两次。
 *
 * 示例 3：
 * 输入：digits = [3,7,5]
 * 输出：[]
 * 解释：
 * 使用给定的 digits 无法构造偶数。
 *
 * 提示：
 *
 * 3 <= digits.length <= 100
 * 0 <= digits[i] <= 9
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/finding-3-digit-even-numbers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode2094 {

    @Test
    public void test01(){
        int[] digits = {2,1,3,0};//[102,120,130,132,210,230,302,310,312,320]
        int[] ints = new Solution1().findEvenNumbers(digits);
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }

}
class Solution1 {
    public int[] findEvenNumbers(int[] digits) {
        //set集合去重
        Set<Integer> set = new HashSet<>();
        //计算当前集合内的三位偶数
        Set<Integer> preSet = new HashSet<>();
        int length = digits.length;
        for (int i = 0; i < length; i++) {
            if (digits[i] == 0 || preSet.contains(digits[i])) {
                continue;
            }
            preSet.add(digits[i]);
            for (int j = 0; j < length; j++) {
                if (j == i) {
                    continue;
                }
                for (int k = 0; k < length; k++) {
                    if (k == j || k == i || digits[k] % 2 != 0) {
                        continue;
                    }
                    int num = digits[i] * 100 + digits[j] * 10 + digits[k];
                    set.add(num);
                }
            }
        }
        //转换为int数组并排序
        int[] ints = set.stream().mapToInt(Integer::valueOf).toArray();
        Arrays.sort(ints);
        return ints;
    }
}

//优化
//class Solution {
//    public int[] findEvenNumbers(int[] digits) {
//        Set<Integer> set = new HashSet<>();
//        // 三层循环，暴力搜索优化版
//        Set<Integer> preset = new HashSet<>();
//        for(int i = 0; i < digits.length; i++) {
//            // 如果第一位为0或者前缀已经遍历过，则继续
//            if (digits[i] == 0 || preset.contains(digits[i])) continue;
//            // 记录前缀出现的数
//            preset.add(digits[i]);
//            for(int j = 0; j < digits.length; j++){
//                // 如果第一位和第二位重复则继续
//                if (i == j) continue;
//                for(int k = 0; k < digits.length; k++){
//                    // 如果第三位和第一位或第二位重复或者第三位的数为奇数则继续
//                    if (digits[k] % 2 != 0 || i == k || j == k) continue;
//                    // 过滤后均是符合条件的数
//                    set.add(digits[i]*100 + digits[j]*10 + digits[k]);
//                }
//            }
//        }
//        int[] arr = new int[set.size()];
//        int idx = 0;
//        for(int i:set){
//            arr[idx++] = i;
//        }
//        Arrays.sort(arr);
//        return arr;
//    }
//}
//
//作者：lin-hua-v
//链接：https://leetcode.cn/problems/finding-3-digit-even-numbers/solution/bao-li-you-hua-by-lin-hua-v-xovb/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
